package cn.zifangsky.array.questions;

import org.junit.Test;

/**
 * 寻找旋转排序数组中的最小值（可能存在重复值）
 *
 * <p>假设一个排好序的数组在其某一未知点发生了旋转（比如 0 1 2 4 5 6 7 可能变成 4 5 6 7 0 1 2 ）。你需要找到其中最小的元素。</p>
 * <p>注意数组中可能存在<b>重复</b>的元素。</p>
 *
 * <ol>
 *     <li>输入：[1, 3, 5]；结果：1</li>
 *     <li>输入：[2, 2, 2, 0, 1]；结果：0</li>
 *     <li>输入：[3, 1, 2]；结果：1</li>
 * </ol>
 *
 * @author zifangsky
 * @date 2020/10/20
 * @since 1.0.0
 */
public class Problem_008_FindTheSmallestValueInARotatedSortedArray {

    /**
     * 测试代码
     */
    @Test
    public void testMethods(){
        int[] arr1 = new int[]{4, 4, 5, 6, 7, 0, 1, 2};
        int[] arr2 = new int[]{3, 4, 5, 1, 2, 2};
        int[] arr3 = new int[]{2, 2, 2, 0, 1};
        int[] arr4 = new int[]{3, 1, 3};
        int[] arr5 = new int[]{3, 3, 1, 3};
        int[] arr6 = new int[]{10, 1, 10, 10, 10};

        //结果：0
        System.out.println("方法一：" + this.findMin1(arr1) + "，方法二：" + this.findMin2(arr1));
        //结果：1
        System.out.println("方法一：" + this.findMin1(arr2) + "，方法二：" + this.findMin2(arr2));
        //结果：0
        System.out.println("方法一：" + this.findMin1(arr3) + "，方法二：" + this.findMin2(arr3));
        //结果：1
        System.out.println("方法一：" + this.findMin1(arr4) + "，方法二：" + this.findMin2(arr4));
        //结果：1
        System.out.println("方法一：" + this.findMin1(arr5) + "，方法二：" + this.findMin2(arr5));
        //结果：1
        System.out.println("方法一：" + this.findMin1(arr6) + "，方法二：" + this.findMin2(arr6));
    }

    /**
     * 方法一（暴力破解）：直接单次循环遍历搜索整个数组找到最小元素，时间复杂度为 O(n)。
     */
    private int findMin1(int[] nums) {
        if(nums == null || nums.length < 1){
            throw new IllegalArgumentException("参数存在异常！");
        }

        int min = Integer.MAX_VALUE;
        for(int num : nums){
            if(num < min){
                min = num;
            }
        }

        return min;
    }

    /**
     * 方法二（改进的二分查找，时间复杂度为O(log(n))）：
     * <ol>
     *     <li>如果 nums[left] < nums[right]，则说明 nums 是有序数组，直接返回 nums[left] 即可</li>
     *     <li>如果 nums[left] < nums[mid]，则说明 nums[left, mid] 是有序数组，最小值在 nums(mid, right] 之间，令 left=mid+1</li>
     *     <li>如果 nums[left] > nums[mid]，则说明 nums[mid, right] 是有序数组，最小值在 nums[left, mid] 之间，令 right=mid</li>
     *     <li>如果 nums[left] = nums[mid]，同时 nums[left] >= nums[right]，可以发现满足这个条件的有以下几种场景：</li>
     *         <ul>
     *             <li>[10, 1]，其中：left=0；mid=0；right=1</li>
     *             <li>[3, 3, 1, 3]，其中：left=0；mid=1；right=3</li>
     *             <li>[1, 1, 1, 1]，其中：left=0；mid=1；right=3</li>
     *             <li>[10, 1, 10, 10, 10]，其中：left=0；mid=2；right=4</li>
     *         </ul>
     *     <li>以上这几种场景，最大的难点是难以判断最小值到底在 nums(mid, right]，还是在nums[left, mid]。
     *     不过在这几种场景中我们可以发现一个共同点，那就是 nums[left] 肯定不是（唯一）最小值，因此我们直接让 left = left + 1
     *     就可以打破这种尴尬判断了。</li>
     * </ol>
     */
    private int findMin2(int[] nums) {
        if(nums == null || nums.length < 1){
            throw new IllegalArgumentException("参数存在异常！");
        }

        int left = 0, right = nums.length - 1;
        while (left < right){
            //1. 最小值在left
            if(nums[left] < nums[right]){
                return nums[left];
            }

            int mid = (right + left) / 2;
            //2. 最小值在(mid, right]
            if(nums[left] < nums[mid]){
                left = mid + 1;
            }
            //3. 最小值在[left, mid]
            else if(nums[left] > nums[mid]){
                right = mid;
            }
            //4. 当 nums[left] = nums[mid]，同时 nums[left] >= nums[right]，具体操作原因见上面方法注释
            else{
                left = left + 1;
            }
        }

        return nums[left];
    }

}
